package com.such.kit.datastructure.tree.bean;

import java.io.Serializable;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedHashMap;
import java.util.List;
import java.util.Map;
import org.apache.commons.collections4.multimap.ArrayListValuedHashMap;
import com.such.kit.file.FileCommons;
import com.such.kit.string.StringCommons;
import com.such.kit.validate.ValidateCommons;

/**
 * @作者 SUCH
 * @日期 2018-10-9 上午11:05:05
 * @描述 树节点
 * @param <T>
 */
public class Tree<T> implements Serializable {

	private static final long serialVersionUID = 3078313881197455405L;

	private String idPathSeparator = "";
	private Map<String, Node<T>> rootStore = new LinkedHashMap<String, Node<T>>();
	private Map<String, String> idPathMap = new HashMap<String, String>();
	private ArrayListValuedHashMap<String, String> unrootIdsStore = new ArrayListValuedHashMap<String, String>();

	public Tree() {
		this.idPathSeparator = FileCommons.COMPAT_SEPARATOR;
	}

	public Tree(String idPathSeparator) {
		this.idPathSeparator = idPathSeparator;
	}

	private void updateIdPath(Node<T> parentNode) {
		String parentIdPath = parentNode.getIdPath();
		Map<String, Node<T>> childStore = parentNode.getChildStore();
		if (ValidateCommons.isNotEmpty(childStore)) {
			for (String id : childStore.keySet()) {
				String idPath = StringCommons.merger(parentIdPath, this.idPathSeparator, id);
				Node<T> node = childStore.get(id);
				node.setIdPath(idPath);
				this.idPathMap.put(id, idPath);
				updateIdPath(node);
			}
		}
	}

	/**
	 * <pre>
	 * 添加或更新节点
	 * 
	 * 注意：程序不会对 node 中的 childStore 做深度处理，node 中的 childStore 会被 tree 记录的子节点覆盖
	 * </pre>
	 * @param node 节点
	 */
	public void add(Node<T> node) {
		String id = node.getId();
		String parentId = node.getParentId();
		String idPath = StringCommons.merger(this.idPathSeparator, id);
		Integer level = 1;
		Map<String, Node<T>> childStore = new LinkedHashMap<String, Node<T>>();
		Node<T> treeNode = get(id);
		Node<T> parentTreeNode = get(parentId);
		if (ValidateCommons.isNotEmpty(treeNode)) {
			childStore = treeNode.getChildStore();
		}
		if (ValidateCommons.isNotEmpty(parentTreeNode)) {
			idPath = StringCommons.merger(parentTreeNode.getIdPath(), this.idPathSeparator, id);
			level = parentTreeNode.getLevel() + 1;
		}
		// 检查 unrootIdsStore
		if (this.unrootIdsStore.containsKey(id)) {
			List<String> childIds = this.unrootIdsStore.get(id);
			for (String childId : childIds) {
				String childIdPath = StringCommons.merger(idPath, this.idPathSeparator, id);
				Node<T> childNode = get(childId);
				childNode.setIdPath(childIdPath);
				childNode.setLevel(level + 1);
				updateIdPath(childNode); // 更新所有下级节点 idPath
				childStore.put(childId, childNode);
				this.idPathMap.put(childId, childIdPath);
				this.rootStore.remove(childId);
			}
			this.unrootIdsStore.remove(id);
		}
		node.setIdPath(idPath);
		node.setLevel(level);
		node.setChildStore(childStore);
		this.idPathMap.put(id, idPath);
		if (ValidateCommons.isEmpty(parentId)) {
			// parentId 为空，为 root 节点，新增或覆盖到 rootStore
			this.rootStore.put(id, node);
		} else if (ValidateCommons.isNotEmpty(parentTreeNode)) {
			// parentNode 非空，新增或覆盖到 parentNode.childStore
			parentTreeNode.addChild(node);
		} else {
			// parentNode 为空，新增或覆盖到 rootStore，同时记录到 unrootIdsStore
			this.rootStore.put(id, node);
			this.unrootIdsStore.put(parentId, id);
		}
	}

	/**
	 * <pre>
	 * 添加或更新节点
	 * 
	 * 注意：程序不会对 node 中的 childStore 做深度处理，node 中的 childStore 会被 tree 记录的子节点覆盖
	 * </pre>
	 * @param nodes 节点集
	 */
	public void add(List<Node<T>> nodes) {
		if (ValidateCommons.isNotEmpty(nodes)) {
			for (Node<T> node : nodes) {
				add(node);
			}
		}
	}

	/**
	 * <pre>
	 * 删除节点
	 * </pre>
	 * @param ids 节点 ids
	 */
	public void delete(String... ids) {
		if (ValidateCommons.isNotEmpty(ids)) {
			for (String id : ids) {
				Node<T> node = get(id);
				if (ValidateCommons.isNotEmpty(node)) {
					String parentId = node.getParentId();
					if (ValidateCommons.isEmpty(parentId)) {
						// parentId 为空，为 root 节点
						this.rootStore.remove(id);
					} else {
						Node<T> parentNode = get(parentId);
						if (ValidateCommons.isNotEmpty(parentNode)) {
							// 从 parentNode 节点删除
							parentNode.remodeChild(id);
						}
					}
				}
			}
		}
	}

	/**
	 * <p>方法名：clear</p>
	 * <p>描述：清空树</p>
	 */
	public void clear() {
		this.rootStore.clear();
		this.idPathMap.clear();
		this.unrootIdsStore.clear();
	}

	/**
	 * <pre>
	 * 获取指定节点
	 * </pre>
	 * @param id 节点 id
	 * @return 节点
	 */
	public Node<T> get(String id) {
		String idPath = this.idPathMap.get(id);
		if (ValidateCommons.isEmpty(idPath)) {
			return null;
		}
		Node<T> child = null;
		Map<String, Node<T>> childStore = this.rootStore;
		String[] ids = idPath.split(this.idPathSeparator);
		for (String _id : ids) {
			if (ValidateCommons.isNotEmpty(_id)) {
				if (ValidateCommons.isEmpty(childStore)) {
					return null;
				}
				child = childStore.get(_id);
				if (ValidateCommons.isEmpty(child)) {
					return null;
				}
				childStore = child.getChildStore();
			}
		}
		return child;
	}

	/**
	 * <p>方法名：getRoots</p>
	 * <p>描述：获取所有根节点</p>
	 * @return Node 列表
	 */
	public List<Node<T>> getRoots() {
		return new ArrayList<Node<T>>(this.rootStore.values());
	}

	/**
	 * <p>方法名：getNodes</p>
	 * <p>描述：获取从根节点到指定节点中的所有节点</p>
	 * @param id 节点 id
	 * @return Node 列表
	 */
	public List<Node<T>> getNodes(String id) {
		String idPath = this.idPathMap.get(id);
		if (ValidateCommons.isEmpty(idPath)) {
			return null;
		}
		List<Node<T>> nodes = new ArrayList<Node<T>>();
		Map<String, Node<T>> nodeStore = this.rootStore;
		String[] ids = idPath.split(this.idPathSeparator);
		for (String _id : ids) {
			if (ValidateCommons.isNotEmpty(_id)) {
				if (ValidateCommons.isNotEmpty(nodeStore)) {
					Node<T> node = nodeStore.get(_id);
					if (ValidateCommons.isNotEmpty(node)) {
						nodes.add(node);
						nodeStore = node.getChildStore();
					}
				}
			}
		}
		return nodes;
	}

}
